package hyy_2022;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 判断是否有效括号
 */
public class _0711_20_IsValid {

    public static void main(String[] args) {
        System.out.println(isValid("()"));
    }

    /**
     * 有效括号
     * @param s
     * @return true:是 false:否
     */
    public static boolean isValid(String s) {
        //字符串为空 或 字符串长度为奇数,则返回false
        if(s == null || s.length() == 0 || s.length() % 2 != 0) {
            return false;
        }

        //用Map表示一对有效括号,key为右括号,value为左括号,设计精妙
        Map<Character,Character> pairs = new HashMap<>();
        pairs.put(')','(');
        pairs.put(']','[');
        pairs.put('}','{');


        //栈
        Deque<Character> stack = new LinkedList<>();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(pairs.containsKey(ch)) {
                //右括号,则出栈一个元素与之匹配
                //栈为空 或 栈顶元素 != 右括号,则未匹配成功
                if(stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
                    return false;
                }
                //匹配成功,则栈顶元素出栈
                stack.pop();
            } else {
                //左括号,则入栈
                stack.push(ch);
            }
        }
        //遍历完成,如栈为空,则说明有效括号匹配成功
        return stack.isEmpty();

    }
}
